/*
    1. 先按每个区间的起点进行升序排序，
    确保遍历时可以顺序合并相邻区间。
    2. 依次遍历并合并有重叠的区间，
    将可以合并的更新右端点，不能合并的则作为新区间加入结果。

*/


// #include <stdlib.h>  // 提供 malloc、qsort、realloc 等内存和排序函数
// #include <string.h>  // 提供 memcpy 用于数组复制

// step 1# 定义比较函数，用于对二维数组按每个区间的左端点排序
int compare(const void* a, const void* b) {
    return (*(int**)a)[0] - (*(int**)b)[0];  // 按区间的起始位置升序排序
}

// step 2# 合并区间主函数
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, 
            int* returnSize, int** returnColumnSizes) {
    // step 3# 对所有区间按左端点从小到大排序
    qsort(intervals, intervalsSize, sizeof(int*), compare);

    // step 4# 分配最大可能数量的空间（每个区间都不重合的最坏情况）
    int** result = (int**)malloc(sizeof(int*) * intervalsSize);  // 存储合并后的结果
    int* colSizes = (int*)malloc(sizeof(int) * intervalsSize);   // 每一行有两个元素

    int idx = 0;  // 当前写入 result 的索引

    // step 5# 遍历所有区间，逐个合并
    for (int i = 0; i < intervalsSize; ++i) {
        int start = intervals[i][0];  // 当前区间的起点
        int end = intervals[i][1];    // 当前区间的终点

        if (idx > 0 && start <= result[idx - 1][1]) {
            // step 6# 可以合并，更新右端点为较大值
            if (end > result[idx - 1][1]) {
                result[idx - 1][1] = end;  // 更新右端点
            }
        } else {
            // step 7# 无法合并，添加新区间到结果中
            result[idx] = (int*)malloc(sizeof(int) * 2);  // 分配一行空间
            result[idx][0] = start;  // 赋值起点
            result[idx][1] = end;    // 赋值终点
            colSizes[idx] = 2;       // 每个区间固定长度为2
            idx++;  // 结果数组向后推进一位
        }
    }

    *returnSize = idx;             // 设置结果数量
    *returnColumnSizes = colSizes;  // 返回每行的列数信息
    return result;                 // 返回合并后的二维数组
}
